/****************************************************
          File Name:insert_sort.c
          Author: Abby Cin
          Mail: abbytsing@gmail.com
          Created Time: Fri 10 Apr 2015 02:28:09 PM CST
*****************************************************/

#include<stdio.h>
#include<stdlib.h>

void insert_sort(long A[], long length)
{
    long j, i, key;
    for(j = 1; j < length; j++)
    {
        key = A[j];
        i = j - 1;
        while(i > -1 && A[i] > key)
        {
            A[i + 1] = A[i];
            i = i -1;
        }
        A[i + 1] = key;
    }
}

void insert_recurse(long A[], long length)
{
    long i, key;
    if(length != 0)
        insert_recurse(A, length - 1);
    i = length - 2;
    key = A[length -1];
    while(i >= 0 && A[i] > key)
    {
        A[i + 1] = A[i];
        i = i -1;
    }
    A[i + 1] = key;
}

int main(int argc, char *argv[])
{
    long len;
    long i;

    len = atol(argv[1]);

    long A[len];
    for(i = 0; i< len; i++)
        A[i] = rand();

    if(argc > 2)
        insert_sort(A, len);
    else
        insert_recurse(A, len);
    /*
    for(i=0; i< len; i++)
        printf("%ld ", A[i]);
        */
    printf("\n");
    return 0;
}
